from functools import cache
from math import inf
from typing import Deque

r = 10000
nums = [True] * r
nums[1] = False
primes = []
for i in range(2, r):
    if nums[i]:
        primes.append(i)
    for j in primes:
        if i * j >= r:
            break
        nums[i * j] = False
        if i % j == 0:
            break


class Solution:
    def minOperations(self, n: int, m: int) -> int:

        if nums[n] or nums[m]:
            return -1

        dp = [inf] * r
        dp[n] = n
        q = Deque()
        q.append(n)
        while q:
            c = q.popleft()
            t, b = c, 1
            while t > 0:
                p = t % 10
                if (
                    p != 9
                    and c + b < r
                    and not nums[c + b]
                    and dp[c + b] > dp[c] + c + b
                    and dp[c] + c + b < dp[m]
                ):
                    dp[c + b] = dp[c] + c + b
                    q.append(c + b)
                if (
                    p != 0
                    and c - b > 0
                    and not nums[c - b]
                    and dp[c - b] > dp[c] + c - b
                    and dp[c] + c - b < dp[m]
                ):
                    dp[c - b] = dp[c] + c - b
                    q.append(c - b)
                t //= 10
                b *= 10
        return dp[m] if dp[m] < inf else -1


so = Solution()
print(so.minOperations(5637, 2034))
# print(s.minOperations(17, 72))
# print(s.minOperations(40, 88))
# print(s.minOperations(10, 12))
